# class TreeNode:
#     def __init__(self,val=0):
#         self.val=val 
#         self.left=None
#         self.right=None

# from collections import deque
# def build_level(lst):
#     root=TreeNode(lst[0])
#     que=deque([root])
#     i,n=1,len(lst)
#     while len(que)>0:
#         cur=que.popleft()
#         if i<n and lst[i]:
#             cur.left=TreeNode(lst[i])
#             que.append(cur.left)
#         if i+1<n and lst[i+1]:
#             cur.right=TreeNode(lst[i+1])
#             que.append(cur.right)
#         i+=2 
#     return root 

# def traversal_level(root):
#     if not root: return
#     ans=[]
#     lst=[]
#     que=deque([root])
#     k,nextk=1,0
#     while len(que)>0:
#         cur=que.popleft()
#         if cur: 
#             lst.append(cur.val)
#             if cur.left:
#                 que.append(cur.left)
#                 nextk+=1 
#             if cur.right:
#                 que.append(cur.right)
#                 nextk+=1 
#         #print('*',lst)
#         if len(lst)==k:
#             k,nextk=nextk,0 
#             ans.append(lst)
#             lst=[] #*

#     return ans 
        

# def traversal_level_2(root):
#     if not root: return
#     lst=[]
#     que=deque([root])
#     while len(que)>0:
#         cur=que.popleft()
#         if cur: 
#             lst.append(cur.val)
#             que.append(cur.left)
#             que.append(cur.right)
#         else: 
#             lst.append(None)
#     i=len(lst)-1
#     while i>=0 and not lst[i]: i-=1
#     return lst[:i+1]
        

from collections import deque
class TreeNode:
    def __init__(self,val=0,left=None,right=None):
        self.val = val 
        self.left = left 
        self.right = right 

def build_level(lst):
    root = TreeNode(lst[0])
    que =deque([root])
    i = 1
    while i<len(lst):
        cur = que.popleft()
        if lst[i]:
            cur.left = TreeNode(lst[i])
            que.append(cur.left)
        if i+1<len(lst) and lst[i+1]:
            cur.right = TreeNode(lst[i+1])
            que.append(cur.right)
        i += 2 
    return root
    

def traversal_level(root):
    que = deque([root])
    ans = []
    while len(que)>0:
        cur = que.popleft()
        if cur:
            ans.append(cur.val)
            if cur.left:
                que.append(cur.left)
            else:
                que.append(None)
            if cur.right:
                que.append(cur.right)
            else:
                que.append(None)
    i = len(ans)-1 
    while not ans[i]: i-=1 
    return ans[:i+1]
    

def traversal_level_2(root):
    que = deque([root])
    ans = []
    next_k = 1 
    while len(que)>0:
        k,next_k = next_k,0 
        tmp = []
        for _ in range(k):
            cur = que.popleft()
            tmp.append(cur.val)
            if cur.left:
                que.append(cur.left)
                next_k += 1 
            if cur.right:
                que.append(cur.right)
                next_k += 1
        ans.append(tmp)
    return ans


    



root=build_level([3,9,20,None,None,15,7])
print(traversal_level(root))
print(traversal_level_2(root))











































# class TreeNode:
#     def __init__(self,val=0,left=None,right=None):
#         self.val=val 
#         self.left=left 
#         self.right=right

# from collections import deque
# def build_level(lst):
#     que=deque()
#     root=TreeNode(lst[0])
#     que.append(root)
#     i=1 
#     while i<len(lst):
#         cur=que.popleft()
#         if lst[i]:
#             cur.left=TreeNode(lst[i])
#             que.append(cur.left)
#         if i+1<len(lst) and lst[i+1]:
#             cur.right=TreeNode(lst[i+1])
#             que.append(cur.right)
#         i+=2 
#     return root

# def traversal_level(root):
#     ans=[]
#     lst=[]
#     k,next_k=1,0
#     que=deque()
#     que.append(root)
#     while len(que)>0:
#         cur=que.popleft()
#         if cur:
#             if cur.left:
#                 que.append(cur.left)
#                 next_k+=1 
#             if cur.right:
#                 que.append(cur.right)
#                 next_k+=1 
#             lst.append(cur.val)
#         if len(lst)==k:
#             k,next_k=next_k,0
#             ans.append(lst)
#             lst=[]
#     return ans 

# def traversal_level_2(root):
#     lst=[]
#     que=deque()
#     que.append(root)
#     while len(que)>0:
#         cur=que.popleft()
#         if cur:
#             que.append(cur.left)
#             que.append(cur.right)
#             lst.append(cur.val)
#         else:
#             lst.append(None)
#     j=len(lst)-1
#     while not lst[j]: j-=1
#     return lst[:j+1]

# root=build_level([3,9,20,None,None,15,7])
# print(traversal_level(root))
# print(traversal_level_2(root))
                





































# # class TreeNode:
# #     def __init__(self,val=0,left=None,right=None):
# #         self.val=val 
# #         self.left=left 
# #         self.right=right
# # from collections import deque 
# # def build_level(lst):
# #     root=TreeNode(lst[0])
# #     que=deque([root])
# #     i=1 
# #     while len(que)>0 and i<len(lst): #***
# #         cur=que.popleft()
# #         if i<len(lst) and lst[i]: 
# #             cur.left=TreeNode(lst[i])
# #             que.append(cur.left)
# #         if i+1<len(lst) and lst[i+1]: 
# #             cur.right=TreeNode(lst[i+1])
# #             que.append(cur.right)
# #         i+=2 #**
# #     return root

# # def levelOrder(root):
# #     if not root: return []
# #     ans=[]
# #     #tmp=[]
# #     que=deque([root])
# #     next_k=1
# #     while next_k>0:
# #         k,next_k=next_k,0
# #         tmp=[]
# #         for _ in range(k):
# #             cur=que.popleft()
# #             tmp.append(cur.val)
# #             if cur.left: 
# #                 que.append(cur.left)
# #                 next_k+=1 
# #             if cur.right:
# #                 que.append(cur.right)
# #                 next_k+=1
# #         ans.append(tmp)
# #     return ans

# # root=build_level([3,9,20,None,None,15,7])
# # print(levelOrder(root))
